import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class DAY0331 {

    public class Gift {
        public int getValue(int[] gifts, int n) {
            // write code here
            //先进行排序
            Arrays.sort(gifts);
            //找排序后中间的值
            int mid=gifts.length/2;
            //判断这个中间值在数组中出现过几次
            int count=0;
            for(int i:gifts){
                if(i==gifts[mid]){
                    count+=1;
                }
            }
            if(count>(n/2)){
                return gifts[mid];
            }
            return 0;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        String str1;
        while ((str1=reader.readLine())!=null){
            String str2=reader.readLine();
            System.out.println(getLen(str1,str2));
        }
    }
    public static int getLen(String str1,String str2){
        //首先得到str1和str2的长度
        char[] ch1=str1.toCharArray();
        char[] ch2=str2.toCharArray();
        int len1= ch1.length;
        int len2= ch2.length;
        //建立一个矩阵
        int[][] array=new int[len1+1][len2+1];
        //对矩阵元素进行初始化
        for (int i = 0; i <=len1; ++i) {
            array[i][0]=i;
        }
        for (int j = 0; j <=len2 ; ++j) {
            array[0][j]=j;
        }
        //开始模拟计算
        for (int i = 1; i <= len1; ++i) {
            for (int j = 1; j <= len2; ++j) {
                //插入操作和删除操作
                array[i][j]=Math.min(array[i][j-1],array[i-1][j])+1;
                //替换操作
                if(ch1[i-1]!=ch2[j-1]){
                    array[i][j]=Math.min(array[i][j],array[i-1][j-1]+1);
                }else {
                    array[i][j] = Math.min(array[i][j], array[i - 1][j - 1]);
                }
            }
        }
        return array[len1][len2];
    }
}
